Algebraic Combinatorics in Mathematical Chemistry. Methods and Algorithms. II. Program Implementation of the Weisfeiler-Leman Algorithm

摘要

The stabilization algorithm of Weisfeiler and Leman has as an input anysquare matrix A of order n and returns the minimal cellular (coherent) algebraW(A) which includes A. In case when A=A(G) is the adjacency matrix of a graph G the algorithmexamines all configurations in G having three vertices and, according to thisinformation, partitions vertices and ordered pairs of vertices into equivalenceclasses. The resulting construction allows to associate to each graph G amatrix algebra W(G):= W(A(G))$ which is an invariant of the graph G. For manyclasses of graphs, in particular for most of the molecular graphs, the algebraW(G) coincides with the centralizer algebra of the automorphism group aut(G).In such a case the partition returned by the stabilization algorithm is equalto the partition into orbits of aut(G). We give algebraic and combinatorial descriptions of the Weisfeiler--Lemanalgorithm and present an efficient computer implementation of the algorithmwritten in C. The results obtained by testing the program on a considerablenumber of examples of graphs, in particular on some chemical molecular graphs,are also included.